/**
 * Created by losor on 2017/3/9.
 */
public class _70_ClimbingStairs {

    public static void main(String[] args) {
        System.out.println( climbStairs(9));
    }

    public static int climbStairs(int n) {
        int[] nums = new int[n+1];
        nums[0] = 0;
        nums[1] = 1;
        nums[2] = 2;
        for (int i = 3; i <= n ; i++) {
            nums[i] = nums[i-1] + nums[i-2];
        }
        return nums[n];

    }
}
